CPU scheduling

Basic Concepts

• The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization

CPU–I/O Burst Cycle

• process execution consists of a cycle of CPU execution and I/O wait.
• Process execution begins with a CPU burst.That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on.
• An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a few long CPU bursts

CPU Scheduler

• Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the CPU scheduler
• a ready queue can be implemented as a FIFO queue, a priority queue, a tree, or simply an unordered linked list.

Preemptive and Nonpreemptive Scheduling

• CPU-scheduling decisions may take place under the following four circumstances:
  • When a process switches from the running state to the waiting state
  • When a process switches from the running state to the ready state
  • When a process switches from the waiting state to the ready state
  • When a process terminates
• When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is nonpreemptive or cooperative. Otherwise, it is preemptive.
• Virtually all modern operating systems including Windows, macOS, Linux, and UNIX use preemptive scheduling algorithms.
• preemptive scheduling can result in race conditions when data are shared among several processes
• Most modern operating systems are now fully preemptive when running in kernel mode

Dispatcher

• The dispatcher is the module that gives control of the CPU’s core to the process selected by the CPU scheduler. This function involves the following:
  • Switching context from one process to another
  • Switching to user mode
  • Jumping to the proper location in the user program to resume that program
• The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency

Scheduling Criteria

• Many criteria have been suggested for comparing CPU-scheduling algorithms:
  • CPU utilization
  • Throughput
  • Turnaround time:Turnaround time is the sum of the periods spent waiting in the ready queue, executing on the CPU, and doing I/O.
  • Waiting time: Waiting time is the sum of the periods spent waiting in the ready queue.
  • Response time:the time from the submission of a request until the first response is produced
• It is desirable to maximize CPU utilization and throughput and to minimize turnaround time, waiting time, and response time.

Scheduling Algorithms

First-Come, First-Served Scheduling

• By far the simplest CPU-scheduling algorithm is the first-come first-serve (FCFS) scheduling algorithm
• The implementation of the FCFS policy is easily managed with a FIFO queue
• On the negative side, the average waiting time under the FCFS policy is often quite long.
• Note also that the FCFS scheduling algorithm is nonpreemptive.

Shortest-Job-First Scheduling

• The SJF scheduling algorithm is provably optimal, in that it gives the minimum average waiting time for a given set of processes.

• The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts. The value of contains our most recent information, while stores the past history.

• The SJF algorithm can be either preemptive or nonpreemptive. Preemptive SJF scheduling is sometimes called shortest-remainingtime-firs scheduling.

Round-Robin Scheduling

• The round-robin (RR) scheduling algorithm is similar to FCFS scheduling, but preemption is added to enable the system to switch between processes. A small unit of time, called a time quantum or time slice, is defined
• The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process
• The performance of the RR algorithm depends heavily on the size of the time quantum
• At one extreme, if the time quantum is extremely large, the RR policy is the same as the FCFS policy. In contrast, if the time quantum is extremely small (say, 1 millisecond), the RR approach can result in a large number of context switches
• Thus, we want the time quantum to be large with respect to the context switch time.

Priority Scheduling

• The SJF algorithm is a special case of the general priority-scheduling algorithm
• Priorities can be defined either internally or externally
• Priority scheduling can be either preemptive or nonpreemptive
• A major problem with priority scheduling algorithms is indefinit blocking, or starvation.A priority scheduling algorithm can leave some low priority processes waiting indefinitely
• Asolution to the problem of indefinite blockage of low-priority processes is aging. Aging involves gradually increasing the priority of processes that wait in the system for a long time
• Another option is to combine round-robin and priority scheduling in such a way that the system executes the highest-priority process and runs processes with the same priority using round-robin scheduling.

Multilevel Queue Scheduling

• Let’s look at an example of a multilevel queue scheduling algorithm with four queues, listed below in order of priority:
  • Real-time processes
  • System processes
  • Interactive processes
  • Batch processes
• Each queue has absolute priority over lower-priority queues

Multilevel Feedback Queue Scheduling

• The multilevel feedback queue scheduling algorithm allows a process to move between queues
• If a process uses too much CPU time, it will be moved to a lower-priority queue. This scheme leaves I/O-bound and interactive processes—which are typically characterized by short CPU bursts —in the higher-priority queues. In addition, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.
• It is the most general CPU-scheduling algorithm.it is also the most complex algorithm

Thread Scheduling

Contention Scope

• On systems implementing the many-to-one (Section 4.3.1) and many-to-many (Section 4.3.3) models, the thread library schedules userlevel threads to run on an available LWP. This scheme is known as process contention scope (PCS), since competition for the CPU takes place among threads belonging to the same process.
• To decide which kernel-level thread to schedule onto a CPU, the kernel uses system-contention scope (SCS)
• Typically, PCS is done according to priority—the scheduler selects the runnable thread with the highest priority to run.

Pthread Scheduling

• On systems implementing the many-to-many model, the PTHREAD_SCOPE_PROCESS policy schedules user-level threads onto available LWPs. The number of LWPs is maintained by the thread library, perhaps using scheduler activations (Section 4.6.5). The PTHREAD_ SCOPE_SYSTEM scheduling policy will create and bind an LWP for each user-level thread on many-to-many systems, effectively mapping threads using the one-to-one policy.
• Note that on some systems, only certain contention scope values are allowed. For example, Linux and macOS systems allow only PTHREAD_SCOPE_SYSTEM.

Multi-Processor Scheduling

multiprocessor now applies to the following system architectures: - Multicore CPUs - Multithreaded cores - NUMA systems - Heterogeneous multiprocessing

Approaches to Multiple-Processor Scheduling

• One approach to CPU scheduling in a multiprocessor system has all scheduling decisions, I/O processing, and other system activities handled by a single processor — the master server. The other processors execute only user code.
• This asymmetric multiprocessing is simple because only one core accesses the system data structures, reducing the need for data sharing
• The downfall of this approach is the master server becomes a potential bottleneck where overall system performance may be reduced.
• The standard approach for supporting multiprocessors is symmetric multiprocessing (SMP), where each processor is self-scheduling
• Note that this provides two possible strategies for organizing the threads eligible to be scheduled:
  • All threads may be in a common ready queue,we could use some form of locking to protect the common ready queue from this race condition,accessing the shared queue would likely be a performance bottleneck
  • Each processor may have its own private queue of threads, it is the most common approach, balancing algorithms can be used to equalize workloads among all processors

Multicore Processors

• most contemporary computer hardware now places multiple computing cores on the same physical chip, resulting in a multicore processor
• when a processor accesses memory, it spends a significant amount of time waiting for the data to become available. This situation, known as a memory stall
• To remedy memory stall, many recent hardware designs have implemented multithreaded processing cores in which two (or more) hardware threads are assigned to each core.
• From an operating system perspective, each hardware thread maintains its architectural state, such as instruction pointer and register set, and thus appears as a logical CPU that is available to run a software thread. This technique—known as chip multithreading (CMT)
• Intel processors use the term hyper-threading (also known as simultaneous multithreading or SMT) to describe assigning multiple hardware threads to a single processing core.
• In general, there are two ways to multithread a processing core: coarse grained and fine-graine multithreading
• It is important to note that the resources of the physical core (such as caches and pipelines) must be shared among its hardware threads, and therefore a processing core can only execute one hardware thread at a time
• two different levels of scheduling
  • On one level are the scheduling decisions that must be made by the operating system as it chooses which software thread to run on each hardware thread (logical CPU).
  • A second level of scheduling specifies how each core decides which hardware thread to run
    • round-robin algorithm
    • dynamic urgency value
• In fact, if the operating system scheduler (the first level) is made aware of the sharing of processor resources, it can make more effective scheduling decisions

Load Balancing

• Load balancing attempts to keep the workload evenly distributed across all processors in an SMP system.
• It is important to note that load balancing is typically necessary only on systems where each processor has its own private ready queue of eligible threads to execute.On systems with a common run queue, load balancing is unnecessary
• There are two general approaches to load balancing: push migration and pull migration.
  • With push migration, a specific task periodically checks the load on each processor and—if it finds an imbalance—evenly distributes the load by moving (or pushing) threads from overloaded to idle or less-busy processors.
  • Pull migration occurs when an idle processor pulls a waiting task from a busy processor.
• The concept of a “balanced load” may have different meanings.
  • One view of a balanced load may require simply that all queues have approximately the same number of threads.
  • Alternatively, balance may require an equal distribution of thread priorities across all queues

Processor Affinity

• The data most recently accessed by the thread populate the cache for the processor. As a result, successive memory accesses by the thread are often satisfied in cache memory (known as a “warm cache”).
• Avoid migrating a thread from one processor to another and instead attempt to keep a thread running on the same processor and take advantage of a warm cache. This is known as processor affinity.
• With private, per-processor ready queues, a thread is always scheduled on the same processor and can therefore benefit from the contents of a warm cache
• When an operating system has a policy of attempting to keep a process running on the same processor—but not guaranteeing that it will do so—we have a situation known as soft affinity
• some systems provide system calls that support hard affinity , thereby allowing a process to specify a subset of processors on which it can run.
• The main-memory architecture of a system can affect processor affinity issues as well, such as NUMA
• Interestingly, load balancing often counteracts the benefits of processor affinity.. Similarly, migrating a thread between processors may incur a penalty on NUMA systems

Heterogeneous Multiprocessing

• some systems are now designed using cores that run the same instruction set, yet vary in terms of their clock speed and power management, including the ability to adjust the power consumption of a core to the point of idling the core. Such systems are known as heterogeneous multiprocessing (HMP).
• For ARM processors that support it, this type of architecture is known as big.LITTLE where higher- performance big cores are combined with energy efficient LITTLE cores

Real-Time CPU Scheduling

• Soft real-time systems provide no guarantee as to when a critical real-time process will be scheduled. They guarantee only that the process will be given preference over noncritical processes.
• Hard real-time systems have stricter requirements. A task must be serviced by its deadline; service after the deadline has expired is the same as no service at all.

Minimizing Latency

• We refer to event latency as the amount of time that elapses from when an event occurs to when it is serviced
• Interrupt latency refers to the period of time from the arrival of an interrupt at the CPU to the start of the routine that services the interrupt.
• One important factor contributing to interrupt latency is the amount of time interrupts may be disabled while kernel data structures are being updated
• The amount of time required for the scheduling dispatcher to stop one process and start another is known as dispatch latency
• The most effective technique for keeping dispatch latency low is to provide preemptive kernels
• The conflict phase of dispatch latency has two components:
  • Preemption of any process running in the kernel
  • Release by low-priority processes of resources needed by a high-priority process
• Following the conflict phase, the dispatch phase schedules the high-priority process onto an available CPU.

Priority-Based Scheduling

• The most important feature of a real-time operating system is to respond immediately to a real-time process as soon as that process requires the CPU.
• Note that providing a preemptive, priority-based scheduler only guarantees soft real-time functionality.
• First, the processes are considered periodic. That is, they require the CPU at constant intervals (periods).
• Once a periodic process has acquired the CPU, it has a fixed processing time , a deadline by which it must be serviced by the CPU, and a period . The relationship of the processing time, the deadline, and the period can be expressed as . The rate of a periodic task is .
• Using a technique known as an admission-control algorithm, the scheduler does one of two things. It either admits the process, guaranteeing that the process will complete on time, or rejects the request as impossible if it cannot guarantee that the task will be serviced by its deadline.

Rate-Monotonic Scheduling

• The rate-monotonic scheduling algorithm schedules periodic tasks using a static priority policy with preemption.
• The shorter the period, the higher the priority; the longer the period, the lower the priority
• The rationale behind this policy is to assign a higher priority to tasks that require the CPU more often

Earliest-Deadline-First Scheduling

• Earliest-deadline-firs (EDF) scheduling assigns priorities dynamically according to deadline.
• The appeal of EDF scheduling is that it is theoretically optimal—theoretically, it can schedule processes so that each process can meet its deadline requirements and CPU utilization will be 100 percent. In practice, however, it is impossible to achieve this level of CPU utilization due to the cost of context switching between processes and interrupt handling.

Proportional Share Scheduling

• Proportional share schedulers operate by allocating T shares among all applications
• Proportional share schedulers must work in conjunction with an admission-control policy to guarantee that an application receives its allocated shares of time

POSIX Real-Time Scheduling

Operating-System Examples

Example: Linux Scheduling

Example: Windows Scheduling

Example: Solaris Scheduling

Algorithm Evaluation

Deterministic Modeling

• One major class of evaluation methods is analytic evaluation
• Deterministic modeling is one type of analytic evaluation.This method takes a particular predetermined workload and defines the performance of each algorithm for that workload

Queueing Models

• The computer system is described as a network of servers. Each server has a queue of waiting processes. The CPU is a server with its ready queue, as is the I/O system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, and so on.This area of study is called queueing-network analysis

• As an example, let be the average long-term queue length (excluding the process being serviced), let be the average waiting time in the queue, and let be the average arrival rate for new processes in the queue (such as three processes per second).

  • Little’s formula：

• queueing models are often only approximations of real systems, and the accuracy of the computed results may be questionable ## Simulations

• To get a more accurate evaluation of scheduling algorithms, we can use simulations. Running simulations involves programming a model of the computer system.

• The data to drive the simulation can be generated in several ways. The most common method uses a random-number generator that is programmed to generate processes, CPU burst times, arrivals, departures, and so on, according to probability distributions

• The distributions can be defined mathematically (uniform, exponential, Poisson) or empirically

• It does not indicate anything about the order of their occurrence. To correct this problem, we can use trace files.

Implementation